今天來看的是 Leetcode 的第一題，編號為 1 的 Two Sum。

問題描述

給定一個整數數組 nums 和一個整數 target，請你在該數組中找出和為 target 的那兩個整數，並返回它們的索引。

參考解法

這裡我們參考 peyman_np 的解法，重點有兩個值得注意的點：

1. 利用字典（Dictionary）：字典的鍵是數字的值，對應的值是該數字在數組中的位置。這使得查詢的時間複雜度降到 O(1)。

2. 利用 enumerate 搭配 for 迴圈：這樣我們可以同時獲得每個元素的索引 i 和其對應的值 value。

解法實現

以下是這個解法的 Python 實現：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, value in enumerate(nums):
            remaining = target - value
            
            if remaining in seen:
                return [i, seen[remaining]]
            else:
                seen[value] = i

解法說明

• 步驟：
  • 我們創建一個空的字典 seen。
  • 遍歷 nums，同時獲得每個數字的索引和數值。
  • 計算 remaining，即當前數字需要的補數，這是通過從 target 減去當前的數字得到的。
  • 如果 remaining 存在於 seen 字典中，則找到了符合條件的兩個數字，返回其索引。
  • 否則，將當前的數字及其索引存入 seen 字典中。

這個解法的時間複雜度是 O(n)，因為我們只遍歷了一次數組，並且查詢和插入字典的操作都是 O(1) 的。

接下來，讓我們繼續探索更多 Leetcode 的題目，幫助大家更好地準備 coding 面試！

系列文章
[Day 1] 刷題從 Neetcode 網站開始
[Day 2] 善用 Python 基本資料結構：集合 Set
[Day 3] 善用 Python 基本資料結構：dictionary